package one;

import java.util.*;
import java.util.PriorityQueue;


public class A011 {


    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ret = new int[n-k+1];
        int cur=0;
        //1.大根堆，按照值跟下标排
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]!=o2[0]? o2[0]-o1[0]:o2[1]-o1[1];
            }
        });
        for(int i=0;i<k;i++) {
            queue.add(new int[]{nums[i],i});
        }
        ret[cur++]=queue.peek()[0];

        for(int i=k;i<n;i++) {
            queue.add(new int[]{nums[i],i});
            //移除不在窗口内的值
            while (queue.peek()[1] <= i-k) {
                queue.poll();
            }
            ret[cur++]=queue.peek()[0];
        }
        return ret;
    }
}
